#include<iostream>
#include<pthread.h>//导入成功
#include<stdlib.h>
#include<cstdlib>
#include<malloc.h>
#include<math.h>
#include<iomanip>
#include<arm_neon.h>
#include <sys/time.h>
#include<math.h>
#include <semaphore.h>
using namespace std;

int N = 2000;
//int num;
float** matrix;
const int thread_num = 7;//常量,开八个线程/还尝试了4个线程
sem_t sem_leader;
sem_t sem_Division[thread_num - 1];
sem_t sem_Elimination[thread_num - 1];
//生成不会出错的测试用例
void m_reset(float** m, int n)
{
    for (int i = 0; i < n; i++)
    {
        // 下三角全部设置为0
        for (int j = 0; j < i; j++)
            m[i][j] = 0;
        //对角线设置为1.0
        m[i][i] = 1.0;
        //上三角设置为随机数
        for (int j = i + 1; j < n; j++)
            m[i][j] = rand() % 100;
    }

    //每一行加上比自己下标小的行
    for (int k = 0; k < n; k++)
        for (int i = k + 1; i < n; i++)
            for (int j = 0; j < n; j++)
                m[i][j] += m[k][j];
}

//定义县城数据结构
typedef struct {
    //int k;//消去的轮次
    int t_id;//线程id
    int num;//矩阵的阶数
}threadParam_t;

//线程函数做消去操作
void* threadFunc(void* param)
{
    threadParam_t* p = (threadParam_t*)param;
    //int k = p->k;//消去的轮次
    int t_id = p->t_id;//线程编号
    int num = p->num;

    for (int k = 0; k < num; k++)
    {
        // t_id 为 0 的线程做除法操作，其它工作线程先等待
        // 这里只采用了一个工作线程负责除法操作，同学们可以尝试采用多个工作线程完成除法操作
        // 比信号量更简洁的同步方式是使用 barrier
        if (t_id == 0)
        {
            for (int j = k + 1; j < num; j++)
            {
                matrix[k][j] = matrix[k][j] / matrix[k][k];
            }
            matrix[k][k] = 1.0;
        }
        else
        {
            sem_wait(&sem_Division[t_id - 1]);// 阻塞，等待完成除法操作
        }

        // t_id 为 0 的线程唤醒其它工作线程，进行消去操作
        if (t_id == 0)
        {
            for (int i = 0; i < thread_num - 1; ++i)
            {
                sem_post(&sem_Division[i]);
            }
        }

        // 循环划分任务
        int size=(num-k)/thread_num;

        for (int i = k + 1 + t_id; i < min(num,k + 1 + t_id+size); i++)
        {
            //消去
            for (int j = k + 1; j < num; ++j)
            {
                matrix[i][j] -= matrix[i][k] * matrix[k][j];
            }
            matrix[i][k] = 0.0;
        }

        if (t_id == 0)
        {
            for (int i = 0; i < thread_num - 1; ++i)
            {
                sem_wait(&sem_leader);// 等待其它 worker 完成消去
            }
            //会不会写1-7对应下面的tid更好？
            for (int i = 0; i < thread_num - 1; ++i)
            {
                sem_post(&sem_Elimination[i]);// 通知其它 worker 进入下一轮
            }
        }
        else
        {
            sem_post(&sem_leader);// 通知 leader, 已完成消去任务
            sem_wait(&sem_Elimination[t_id-1]); // 等待通知，进入下一轮
        }
    }

    pthread_exit(NULL);
    return NULL;
}

void solve(int n)
{
    sem_init(&sem_leader, 0, 0);
    for (int i = 0; i < thread_num-1; i++)
    {
        sem_init(sem_Division, 0, 0);
        sem_init(sem_Elimination, 0, 0);
    }

    pthread_t handles[thread_num];
    threadParam_t param[thread_num];

    for (int t_id = 0; t_id < thread_num; t_id++)
    {
        param[t_id].t_id = t_id;
        param[t_id].num = n;
        pthread_create(&handles[t_id], NULL, threadFunc, (void*)(param + t_id));
    }

    //结束线程
    for (int t_id = 0; t_id < thread_num; t_id++)
        pthread_join(handles[t_id], NULL);

}


int main()
{
    matrix = new float* [N];
    for (int i = 0; i < N; i++)
    {
        matrix[i] = new float[N];
    }

    int size = 32;//数据集增长速度
    long long head1, tail1, freq1;//记录串行时间
    struct timeval start1, end1;//
    for (int n = size; n < N; n += size)
    {
        m_reset(matrix, n);

        gettimeofday(&start1, NULL);
        gettimeofday(&end1, NULL);
        int count1 = 0;
        while ((end1.tv_sec - start1.tv_sec) < 1) {
            solve(n);
            gettimeofday(&end1, NULL);
            count1++;
        }
        float time1 = ((end1.tv_sec - start1.tv_sec) * 1000 + float((end1.tv_usec - start1.tv_usec)) / 1000) / count1;


        cout << "问题规模 " << n << " 静态+信号量平均时间 " << time1 << " ms";
        cout << endl;
        if (n > 320) size = 128;
    }

    sem_destroy(&sem_leader);
    sem_destroy(sem_Division);
    sem_destroy(sem_Elimination);
}